class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        function<bool(int, int, int)> valid =
            [&](int left, int right, int rootPos) {
            if (left > right) return true;
            int rootVal = pushed[rootPos];
            int pos = -1;
            for (int i = left; i <= right; ++i) {
                if (popped[i] == rootVal) {
                    pos = i;
                    break;
                }
            }
            if (pos == -1) return false;
            return
                valid(left, pos - 1, rootPos + 1) &&
                valid(pos + 1, right, rootPos + pos - left + 1);
        };
        return valid(0, pushed.size() - 1, 0);
    }
};